package 代码题.动态规划题目;

/**
 * KMP是字符串比较算法
 * 一个随机字符串，另一个是给定的模式字符串
 * 在随机字符串中查找模式字符串出现的第1个位置
 *
 * 使用状态转移方程：dp[0]['a']=1
 * 表示模式字符串的第0个状态在遇到字符a的时候，变成了第1个状态
 *
 *
 * 还有1个影子状态X, 当没匹配到值是。dp[0]['a']=dp[X]['a']
 * 影子状态的转移：X=dp[X]['b']
 *
 * 模式的状态转移方程，使用字符串abcab,
 * 那么影子状态转移方程，就是使用字符串bcab，和原始字符串相差第一个字符
 */
public class KMP {

    public static void main(String[] args) {
        System.out.println(kmpmatcher("aaabaaac","aaac"));
        System.out.println(kmpmatcher("abcd","fgr"));
    }


    public static int  kmpmatcher(String des, String matcher){
        int dlen = des.length();
        int mlen = matcher.length();

        // dp[状态][字符] = 下个状态,  最后一个状态不需要专门存储，可以不存
        int[][] dp = new int[mlen][256];
        dp[0][matcher.charAt(0)] = 1;

        //1.构造模式字符串的状态数组，构造影子状态机
        //影子状态 X 初始为 0，基于模式状态机数组的处理
        //X和j类似于快慢指针
        int X = 0;
        for (int j = 1; j < mlen; j++) {
            for (int c = 0; c < 256; c++) {     //内部的这种循环，每次只能找到一个有效的状态转移值
                if (matcher.charAt(j) == c)
                    dp[j][c] = j + 1;
                else
                    dp[j][c] = dp[X][c];    //回退委托给影子状态
            }

            //当前是状态X，遇到模式字符串的字符matcher.charAt(j)，更新影子状态
            X = dp[X][matcher.charAt(j)];
        }

        //2.使用随机字符串去匹配状态机
        int j = 0;
        for (int i = 0; i < dlen; i++) {
            // 当前是状态 j，遇到字符haystack.charAt(i)，得到最新状态
            j = dp[j][des.charAt(i)];

            if (j == mlen) {
                return i - mlen + 1;
            }
        }
        return -1;
    }
}
